package mht.practice.ListNode;

import java.util.HashMap;

/**
 * Created by MHT on 2017/9/15.
 */
public class getFirstNodeInCycle {
    /**
     * 求进入环中的第一个节点 用快慢指针做
     */
    public static ListNode getFirstNodeInCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        // 1） 找到快慢指针相遇点
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) { // Collision
                break;
            }
        }

        // 错误检查，这是没有环的情况
        if (fast == null || fast.next == null) {
            return null;
        }

        // 2）现在，相遇点离环的开始处的距离等于链表头到环开始处的距离，
        // 这样，我们把慢指针放在链表头，快指针保持在相遇点，然后
        // 同速度前进，再次相遇点就是环的开始处！
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }

        // 再次相遇点就是环的开始处
        return fast;
    }

    /**
     * 求进入环中的第一个节点 用HashMap做 一个无环的链表，它每个结点的地址都是不一样的。
     * 但如果有环，指针沿着链表移动，那这个指针最终会指向一个已经出现过的地址 以地址为哈希表的键值，每出现一个地址，就将该键值对应的实值置为true。
     * 那么当某个键值对应的实值已经为true时，说明这个地址之前已经出现过了， 直接返回它就OK了
     */
    public static ListNode getFirstNodeInCycleHashMap(ListNode head) {
        HashMap<ListNode, Boolean> map = new HashMap<ListNode, Boolean>();
        while (head != null) {
            if (map.get(head) == true) {
                return head; // 这个地址之前已经出现过了，就是环的开始处
            } else {
                map.put(head, true);
                head = head.next;
            }
        }
        return head;
    }
}
